package leetcode;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

//任意结点到任意结点，求最大路径和
public class BinaryTreeMaximumSum {

	public static void main(String[] args) {
		int[] pre = {9, 6, -3, -8, 2, 2, -7, -6};
		int[] in = {6, 9, -8, -3, 2, -7, 2, -6};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		BinaryTreeMaximumSum object = new BinaryTreeMaximumSum();
		System.out.println(object.maxPathSum(root));
	}
	
	public int maxPathSum(TreeNode root) {
        if(root == null){
        	return 0;
        }
        int[] maxValue = new int[1];
        maxValue[0] = Integer.MIN_VALUE;
        int res = getMaxPathSum(root, maxValue);
        return Math.max(res, maxValue[0]);
    }
	
	//返回的是离root最大的pathSum, maxValue表示的是子树最大的pathSum
	public int getMaxPathSum(TreeNode root, int[] maxValue){
		int leftPathSum = root.val;
		int rightPathSum = root.val;
		int leftMax = Integer.MIN_VALUE;
		int rightMax = Integer.MIN_VALUE;
		// System.out.println("curRoot: " + root.val);
		if(root.left != null){
			//之前一直不通过，因为这里要判断最大值是否超过了0
			int temp = getMaxPathSum(root.left, maxValue);
			if(temp > 0){
				leftPathSum += temp;
			}
			leftMax = maxValue[0];
		}
		// System.out.println("leftPathSum :" + leftPathSum);
		if(root.right != null){
			int temp = getMaxPathSum(root.right, maxValue);
			if(temp > 0){
				rightPathSum += temp;
			}
			rightMax = maxValue[0];
		}
		// System.out.println("rightPathSum :" + rightPathSum);
		maxValue[0] = getMax(root.val, leftPathSum , rightPathSum , leftMax, rightMax);
		// System.out.println("maxValue :" + maxValue[0]);
		return Math.max(leftPathSum, rightPathSum);
	}
	
	//由于我们已经判断了left和right是否超过0，那么肯定是大于a的了
	public int getMax(int a, int left, int right, int c, int d){
//	    int val = a;
//	    if(left - val > 0){
//	        a += left - val;
//	    }
//	    if(right - val> 0){
//	        a += right - val;
//	    }
	    a = left + right - a;
		int max = Math.max(d, c);
		int res = Math.max(a, max);
		return res;
	}
}
